package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var balance bool

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	balance = true
	dfs1(root)
	return balance
}

func dfs1(root *TreeNode) int {
	leftHeight := 0
	if root.Left != nil {
		leftHeight = dfs1(root.Left)
	}
	rightHeight := 0
	if root.Right != nil {
		rightHeight = dfs1(root.Right)
	}
	if leftHeight-rightHeight > 1 || leftHeight-rightHeight < -1 {
		balance = false
	}
	if leftHeight > rightHeight {
		println(root.Val, leftHeight+1)
		return leftHeight + 1
	} else {
		println(root.Val, rightHeight+1)
		return rightHeight + 1
	}
}

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
				Left: &TreeNode{
					Val: 4,
				},
				Right: &TreeNode{
					Val: 4,
				},
			},
			Right: &TreeNode{
				Val: 3,
			},
		},
		Right: &TreeNode{
			Val: 2,
		},
	}
	println(isBalanced(root))
}
